Contest Nodeocder1100

发表于 | 更新于 | 分类于 | 评论数：
Nowcoder CSP-J提高组s赛前集训营

仓鼠的石子游戏

有$N$个石圈，每个石圈有$A[i]$个石头围成一圈，有两个人轮流对石子进行染色，相邻不能同色，首先不能操作的一方输，求先手必赢还是后手必赢。

这个题叭，说是博弈论，但是比较好推。首先讨论只有一个石圈的情况。那么我们发现对于偶数个的话，我们类比“放盘子问题”，对于先手放的每一个石头，我们都放到过石圈中点的对称位置，那么先手一定先不能走。

再讨论奇数的时候，我们后手每一次都放到先手的相邻位置，那么我们依然必赢。也就是说对于一个石圈，无论是奇数还是偶数（1除外），先手都是必输的。

但是唯一的不同之处就在于1，1的时候先手是必赢的。

那么转而来看多个石圈，你会发现没有任何不同，你可能会认为对于一个圈$A[i]$，先手某一次不放$A[i]$而转战$A[j]$就会改变$A[i]$里面的先后手顺序。但是没有关系，我们后手只需要也转战$A[j]$就可以了。

这个时候我们会发现1仍然是个唯一的特例。所以我们手推几组样例就会发现奇数个1就是先手赢，而偶数个1就是后手赢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define int LL

#define LS (Now << 1)
#define RS ((Now << 1) | 1)
#define Mid ((L + R) >> 1)
#define E_Mid ((G[Now].L + G[Now].R) >> 1)

using namespace std ;

typedef long long LL ;
const int MAXN = 1010 ;
const int MAXM = 1010 ;
const int INF = 0x7fffffff ;
int T, N, A[MAXN], Ans ;

inline int Read() {
    int X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0')
        F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9')
        X = (X << 1) + (X << 3) + (ch ^ 48), ch = getchar() ;
    return X * F ;
}

signed main() {
    T = Read() ; while (T --) {
        N = Read() ; Ans = 0 ;
        for (int i = 1 ; i <= N ; i ++) {
            A[i] = Read() ;
            if (A[i] == 1) Ans ++ ;
        }
        if (Ans & 1) puts("rabbit") ;
        else puts("hamster") ;
    }
    return 0 ;
}

乃爱与城市拥挤程度

给你一棵树，问你每个节点作为根的时候距离小于$K$的节点的个数以及这些节点动态权值的乘积。

这是个换根DP。
首先对于第一问，我们设$Dp[i][j]$表示$i$点在$j$布以内的点数，那么转移的时候就转移到与自己联通的其他节点上，然后我们去除重复计算的j-2步向其他方向扩散的状态，就得到$Dp$方程：

（D表示度。）

对于第二问，我们考虑先随便找到一个根然后进行换根。我们先把随便找到的根进行Dp，然后储存起来。对于每一次换根，假设我们要从$X$转换到$Y$，那么对于$X$我们做一个自下而上的Dp，然后对于$Y$我们再做一个自上而下的Dp，然后合并一下就可以了。

（说白了还是瞎搞）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define LS (Now << 1)
#define RS ((Now << 1) | 1)
#define Mid ((L + R) >> 1)
#define E_Mid ((G[Now].L + G[Now].R) >> 1)

using namespace std ;

typedef long long LL ;
const int MAXN = 100010 ;
const int MAXM = 15 ;
const int INF = 0x7fffffff ;
const int mod = 1e9 + 7 ;

int N, K, H[MAXN], T, f[MAXN][MAXM], g[MAXN][MAXM] ;
long long F[MAXN][MAXM], G[MAXN][MAXM], Ans[MAXN] ;
int Tot[MAXN] ;
struct node {
    int p, nxt;
    node(int P = 0, int Nxt = 0) {
        p = P;
        nxt = Nxt;
    }
} Line[MAXN << 2] ;

inline int Read() {
    int X = 0,  F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0')
        F = (ch == '-' ?  -  1 : 1),  ch = getchar() ;
    while (ch >= '0' && ch <= '9')
        X = (X << 1) + (X << 3) + (ch ^ 48),  ch = getchar() ;
    return X  *  F ;
}

long long kasumi(long long base,  int K) {
    long long res = 1 ;
    while(K) {
        if(K & 1) res = (res  *  base)  %  mod;
        K >>= 1 ;
        base = (base  *  base)  %  mod;
    }	return res ;
}

void add() {
    int A = Read(),  B = Read() ;
    Line[ ++  T] = node(B,  H[A]) ; H[A] = T ;
    Line[ ++  T] = node(A,  H[B]) ; H[B] = T ;
}

void predfs(int now, int fa = 0) {
    f[now][0]=1;
    for(int i = H[now];i ; i = Line[i].nxt) {
        int v = Line[i].p;
        if(v==fa) continue;
        predfs(v, now);
        for(int j = 1 ; j <= K; ++ j)
            f[now][j]+=f[v][j - 1];
    }
    return ;
}

void dfs(int now, int fa = 0) {
    for(int i = 0 ; i <= K ; i ++ ) Tot[now]+=g[now][i];
    for(int i = H[now];i ; i = Line[i].nxt) {
        int v = Line[i].p ;
        if(v==fa) continue ;
        g[v][0]=f[v][0] ;
        g[v][1]=f[v][1] + f[now][0] ;
        for(int j = 2 ; j <= K; ++ j)
            g[v][j]=f[v][j]+(g[now][j - 1] - f[v][j - 2]) ;
        dfs(v, now) ;
    }
    return ;
}

void dfs1(int now, int fa = 0) {
    for(int i = 0 ; i <= K; ++ i) F[now][i]=1;
    for(int i = H[now];i ; i = Line[i].nxt) {
        int v = Line[i].p;
        if(v==fa) continue;
        dfs1(v, now);
        for(int j = 1 ; j <= K; ++ j)
            F[now][j]=(F[now][j] * F[v][j - 1]) % mod;
    }
    for(int i = 1, t = 1 ; i <= K; ++ i) {
        t+=f[now][i];
        F[now][i]=(F[now][i] * t) % mod;
    }
    return ;
}

void dfs2(int now, int fa = 0) {
    Ans[now]=G[now][K];
    for(int i = H[now];i ; i = Line[i].nxt) {
        int v = Line[i].p;
        if(v==fa) continue;
        G[v][0]=F[v][0];
        G[v][1]=(((F[v][1] * F[now][0] % mod) * kasumi(f[v][1], mod - 2)) % mod * g[v][1]) % mod;
        for(int i = 2 ; i <= K; ++ i)
            G[v][i]=((((F[v][i] * kasumi(f[v][i], mod - 2) % mod * G[now][i - 1]) % mod * kasumi(g[now][i - 1], mod - 2)) % mod * kasumi(F[v][i - 2], mod - 2)) % mod * g[v][i]) % mod * (g[now][i - 1] - f[v][i - 2]) % mod;
        dfs2(v, now);
    }
}

signed main() {
    N = Read() ; K = Read() ;
    for(int i = 1 ; i < N ; ++ i) add();
    predfs(1);
    for(int i = 0 ; i <= K ; ++ i) g[1][i]=f[1][i];
    dfs(1);
    for(int i = 1 ; i <= N ; ++ i) printf("%d ", Tot[i]) ;
    printf("\n"); dfs1(1);
    for(int i = 1 ; i <= N ; ++ i) for(int j = 1 ; j <= K; ++ j)
        g[i][j]+=g[i][j - 1], f[i][j]+=f[i][j - 1];
    for(int i = 0 ; i <= K ; ++ i) G[1][i]=F[1][i];
    dfs2(1);
    for(int i = 1 ; i <= N ; ++ i) printf("%lld ", G[i][K]) ;
    return 0;
}

小w的魔术扑克

$K$具有正反面的卡片，打出时只能选择一面，查询$Q$次，每次问是否能组成$L$到$R$的顺子。

智障死了，这个题。
发现30pts特别好拿，时间不是很充足了就弄了个匈牙利匹配，然后用前缀和特判一下10分的正反相同的情况勉勉强强拿到了40分。考场上只写出来了这些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define LS (Now << 1)
#define RS ((Now << 1) | 1)
#define Mid ((L + R) >> 1)
#define E_Mid ((G[Now].L + G[Now].R) >> 1)

using namespace std ;

typedef long long LL ;
const int MAXN = 100010 ;
const int MAXM = 100010 ;
const int INF = 0x7fffffff ;

int N, K, Q, Girl[MAXN], Use[MAXN], V[MAXN] ;
int Sum[MAXN], F = 1, H[MAXN], Tot ;
struct NODE {
    int F, T, Next ;
}   E[MAXN << 1 * 10] ;

inline void Add(int F, int T) {
    E[++ Tot].F = F ; E[Tot].T = T ;
    E[Tot].Next = H[F], H[F] = Tot ;
}
inline int Read() {
    int X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0')
        F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9')
        X = (X << 1) + (X << 3) + (ch ^ 48), ch = getchar() ;
    return X * F ;
}

inline bool Find(int Now) {
    for(int i = H[Now] ; i ; i = E[i].Next)
		if (! Use[E[i].T]){
			Use[E[i].T] = 1 ;
			if(! Girl[E[i].T] || Find(Girl[E[i].T])){
				Girl[E[i].T] = Now ;
				return true ;
			}
		}
	return false;
}

signed main(){
    freopen("ex.in", "r", stdin) ;
    freopen("ex2.out", "w", stdout) ;
    N = Read() ; K = Read() ;
    for (int i = 1 ; i <= K ; i ++) {
        int A = Read(), B = Read() ;
        Add(A, i) ; Add(B, i) ;
        if (A != B) F = 0 ;
        V[A] = 1 ; V[B] = 1 ;
    }
    if (F == 1) {
        for (int i = 1 ; i <= N ; i ++)
            if (V[i]) Sum[i] = Sum[i - 1] + 1 ;
            else Sum[i] = Sum[i - 1] ;
        Q = Read() ;
        for (int i = 1 ; i <= Q ; i ++) {
            int L = Read(), R = Read() ;
            if (Sum[R] - Sum[L - 1] == R - L + 1)
                puts("Yes") ;
            else puts("No") ;
        }
        return 0 ;
    }
    Q = Read() ;
    for (int i = 1 ; i <= Q ; i++) {
        memset(Girl, 0, sizeof (Girl)) ;
        int L = Read(), R = Read(), Ans = 0 ;
        for (int i = L ; i <= R ; i ++) {
            memset(Use, 0, sizeof (Use)) ;
		    Ans += Find(i) ;
        }
        if (Ans == R - L + 1) printf("Yes\n") ;
        else printf("No\n") ;
    }
	return 0 ;
}

然后我们考虑正解。

如果能想到图论模型，这个题就解了一半了。对于每个面值，由于在一个查询中它最多需要一次。所以我们可以把每个面值都当成是一个节点，对于一张牌，我们都建一条连接它正反两面两个面值的边。建好模型以后，我们不难发现，如果对于一个大小为N的连通块有至少N条边，那么这个连通块一定能满足保证每个面值都能够被提供至少一次。只有一种连通块特殊，也就是当连通块的大小为N，并且它具有N-1条边时，无论怎么调整，都会漏掉一个面值无法打出，大小为N，具有N-1条边的连通块，那也就是树。

所以我们先找树，dfs并查集啥玩意都ok，总之找出所有的树就可以了。

然后我们想这个问题的反面：什么样的顺子是不能满足的，我们发现，如果你的顺子完全包含了一颗树，那这个顺子就由于上述的原因无法构造。问题来了？如何判断一个顺子是否完全包含树？

先求出每一颗树上节点编号的最小值与最大值，构造一个约束线段，约束线段的左端点为树上节点编号的最小值，右端点为树上节点编号的最大值。

接下来问题转化成了线段覆盖问题：

即：给定查询线段l,r，问你查询线段是否至少完整的覆盖了任意一个约束线段。如果存在则输出No，反之输出Yes。

这个就是个经典问题了，按照线段的右端点排序然后离线树状数组。对于每一个约束线段都将它的左端点赋成1，然后查询，查询区间和是否为0即可。

当然你也可以使用桶排序或者链式前向星处理查询，然后离线扫描线for过去维护下界。这样做是近似O(n)复杂度的算法，因为第一步使用了并查集，所以全局复杂度不是O(n)，而是O(nlogn)，只不过并查集常数太小了所以一般近似O(n)。

$T3$以上正解来自官方题解。

本文标题:Contest Nodeocder1100

文章作者:Sue Shallow

发布时间:2019年10月29日 - 22:16:31

最后更新:2019年11月11日 - 19:52:39

原始链接:http://Yeasion.github.io/2019/10/29/Contest Nowcoder1100/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。